题意

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

与[LeetCode 15. 3Sum]类似，只不过这里a b c和的目标值变成了变量，求与目标变量最接近的那个a b c的和。

思路

[LeetCode 15. 3Sum]中要求a+b+c=0，而这里则是a+b+c=target，因此在枚举确定a+b后只需要把[LeetCode 15. 3Sum]中算法的二分搜索目标由-c改为target-c即可。

具体实现时可以使用stl::lower_bound()函数来找大于等于c-target的第一个数，找到后根据返回的情况判断这个数周围的一个数是否可能成为更优解，注意检查周围可能的更优解时访问不要越界。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int mindis = 0x7ffffff;
        int ret = 0;
        bool find = false;
        sort(nums.begin(),nums.end());
        int len = nums.size();
        for(int i = 0; !find && i < len; i++)
        {
            for(int j = i + 1; !find && j < len - 1; j++)
            {
                int tar = target - nums[i] - nums[j];
                int index = lower_bound(nums.begin() + j + 1, nums.end(), tar) - nums.begin();
                if(index < len)
                {
                    if(nums[index] == tar)
                    {
                        mindis = 0;
                        ret = nums[i] + nums[j] + nums[index];
                        find = true;
                        break;
                    }
                    else
                    {
                        if(index == j + 1)
                        {
                            int d = nums[index] - tar;
                            if(mindis > d)
                            {
                                mindis = d;
                                ret = nums[i] + nums[j] + nums[index];
                            }
                        }
                        else
                        {
                            int d[2] = {tar - nums[index - 1], nums[index] - tar};
                            bool swaped = false;
                            if(d[0] > d[1])
                            {
                                swap(d[0], d[1]);
                                swaped = true;
                            }
                            if(mindis > d[0])
                            {
                                mindis = d[0];
                                if(swaped)
                                {
                                    ret = nums[i] + nums[j] + nums[index];
                                }
                                else
                                {
                                    ret = nums[i] + nums[j] + nums[index-1];
                                }
                            }
                        }
                    }
                }
                else //index == len
                {
                    if(mindis > tar - nums[len - 1])
                    {
                        mindis = tar - nums[len - 1];
                        ret = nums[i] + nums[j] + nums[len - 1];
                    }
                }
                while(!find && j < len && nums[j] == nums[j+1]) j++;
            }
            while(!find && i < len && nums[i] == nums[i+1]) i++;
        }
        return ret;
    }
};